Subject: Flow Control Proposal

From: "Shannon Nix" <[email-masked]>
Date: Wed, 22 Jun 94 12:04:09

Greetings,
          
          Sorry this is so late.  I've tried to pull together the following.
          
          a.  The original proposal
          b.  + Peter's comments
          c.  + feedback proposal
                  1.  Cumulative
                  2.  Sender responds immediately
          
          Due to the feedback mechanism, I have renamed the following
          
          1. Pacing Response (PRSP) IS NOW  Flow Control Indicator ( FCIND)
          2. Pacing Request  (PREQ) IS NOW  Flow Control Acknowledgment ( FCACK)
          
          Please review attachment and come prepared to discuss.
          
          Regards, Shannon

1.0    Introduction

This document specifies a flow control protocol for Data Link Switching 
(DLSw) and to propose its adoption by DLSw Related Interest Group (RIG) 
to a status of Approved Direction (AD).

1.1    Purpose

The document is intended to specify extensions to the Switch-to-Switch 
Protocol (SSP) of DLSw which will allow a pair of DLSw partner nodes to
efficiently share network resources among the multiple circuits which
may be multiplexed across their common transport connection.

It is beyond the scope of this document to specify a particular policy
for resource sharing, but rather to incorporate into the protocol a mechanism
enabling the implementation of such policies.

2.0	Terms and Notation

3.0     Protocol Extensions

3.1     Basic Overview

Each session shall consist of two data flows, one in each direction.  Each
data flow shall have its own independent flow control mechanism.  For each 
data flow there is an entity that originates traffic, referred to as the 
sender, and a target entity which receives the traffic, referred to as the 
receiver.

A sender may only send data when its receiver has granted explicit permission
to send a discreet number of data units.  Data units shall be defined as
either a DGRMFRAME or an INFOFRAME.  

The receiver shall grant permission to send data units by sending a Flow 
Control Indicator (FCIND - defined later.  The sender must acknowledge all 
FCINDs by sending a Flow Control Acknowledgment (FCACK- defined later).

A sending implementation must maintain these values:

   1.  GrantedUnits - The number of units (frames) which the sender
       currently has permission to send.
       
   2.  CurrentWindow - This is a discreet number of units, controlled by 
       the receiver, which is basis for granting additional units.
       
   3.  InitialWindowSize - Global for all circuits on a transport connection.
       Learned in capabilities exchange when the transport connection is 
       established.  It specifies an initial value for CurrentWindow when
       each circuit is established.
           
A receiving implementation must maintain these values: 

   1.  CurrentWindow - This is a discreet number of units, controlled by 
       the receiver, which is basis for granting additional units.
       
   2.  InitialWindowSize - Global for all circuits on a transport connection.
       Sent in capabilities exchange when the transport connection is 
       established.  It specifies an initial value for CurrentWindow when
       each circuit is established.
       
   3.  FCACKOwed - The sender owes an FCACK.  If true, no FCIND may be sent.       
           
3.2    Frame Format       

The following diagram describes the relevant header format of a DLSw 
information message (INFOFRAME):

       +-----------------------+------------------------+
Byte 0 | Version               | Flow Control Byte      |
       +-----------------------+------------------------+
Byte 2 | Message Length                                 |
       +-----------------------+------------------------+
Byte 4 | Remote Data Link Correlator                    |
       |                       +                        |
Byte 6 |                                                |
       +-----------------------+------------------------+
...    |  ...                                           |
       
The following diagram describes the relevant header format of a DLSw 
control message (DGRMFRAME):

       +-----------------------+------------------------+
Byte 0 | Version               | Flow Control Byte      |
       +-----------------------+------------------------+
Byte 2 | Message Length                                 |
       +-----------------------+------------------------+
Byte 4 | Remote Data Link Correlator                    |
       |                       +                        |
Byte 6 |                                                |
       +-----------------------+------------------------+
...    |  ...                                           |
       
NOTE: From a flow control perspective, the two frame headers
      are handled identically.       
       
The following diagram describes the format of the Flow Control Byte

bit   0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
    |FCI FCA|  FCO  |    reserved   |
    +---+---+---+---+---+---+---+---+

FCI : Flow Control Indicator 
FCA : Flow Control Ack
FCO : Flow Control Operator Bits

      00 - Repeat Window Operator
      01 - Increment Window Operator
      10 - Decrement Window Operator
      11 - Reset Window Operator

A frame with the FCI bit set shall be referred to as a Flow Control
Indication (FCIND).  An FCIND is used to manage the flow in the opposite
direction of the frame which bears it.

A frame with the FCA bit set shall be referred to as a Flow Control
Acknowledgment (FCACK).  An FCACK is used to manage the flow in the same
direction of the frame which bears it.

NOTE:  A frame may be both a FCIND and an FCACK.

A frame bearing an FCIND or FCACK may also contain data for the flow in
the direction it is traveling.  In such a frame, the FCIND or FCACK are 
said to be  piggy-backed.  A non-piggy-backed FCIND is called an Independent 
Flow Control Indication (IFCIND) and a non-piggybacked FCACK is called an
Independent Flow Control Acknowledgment (IFCACK).

NOTE:  A frame may be both an IFCIND and an IFCACK.

3.3     Granting Permission to Send Data

A receiver shall grant a sender permission to send units of data by sending
FCIND.  Each FCIND is further qualified by a flow control operator, which 
is encoded in the FCO bits of the FCIND header. With one exception (the
Reset Window operator) all operators may be either piggy-backed carried
in a IFCIND.

The four flow control operators are outlined below:

3.3.1.  Repeat Window Operator
           
This operator shall be processed as follows:

(CurrentWindow unchanged)
GrantedUnits += CurrentWindow
          
3.3.2.  Increment Window Operator
   
This operator shall be processed as follows:

          CurrentWindow++
          GrantedUnits += CurrentWindow
          
3.3.3.  Decrement Window Operator
   
This operator shall be processed as follows:

          CurrentWindow--
          GrantedUnits += CurrentWindow
          
NOTE:  This operator may only be sent if CurrentWindow is greater than one.          
          
3.3.4.  Reset Window Operator
   
This operator shall be processed as follows:

          CurrentWindow = 0;
          GrantedUnits  = 0;

NOTE:  This operator may only flow on an independent pacing indication ( may NOT 
       be piggy-backed).

NOTE:  After sending this operator, the only legal subsequent operator shall 
       be Increment Window.

3.4     Acknowledging a Flow Control Operator

Each sender must acknowledge each FCIND with an FCACK which is piggy-backed
on the next frame in the opposite direction in all cases except the
Reset Window Operator.

The receiver may have no more than one unacknowledged FCIND outstanding
at any time with one exception:  A Reset Window Operator may be sent
while another FCIND is pending acknowledgment. 

NOTE: The FCI and FCO bits of the FCACK are used independently by 
the flow in the opposite direction

3.4.1   Acknowledging a Reset Window Operator

Since this operator revokes all previously granted units, the sender
must acknowledge this FCIND using an IFCACK (Independent Flow Control
Acknowledgment).  This is the only case where IFCACK is used.

Should a sender receive a non-reset FCIND followed by a Reset Window
FCIND before acknowledging the first, he shall only acknowledge the
Reset Window.

NOTE: The FCI and FCO bits on these frames are used independently by
the flow in the opposite direction.

3.5	Capabilities Exchange

When two standards-level nodes establish a transport connection, they
shall engage in a capabilities exchange.  This protocol of this exchange
is beyond the scope of this document.  

It should be noted, however, that the two nodes shall be required to 
exchange the following parameter:

InitialWindowSize -  This shall indicate to the partner what the sending
                     flow entity shall initialize its CurrentWindow
                     value two for each multiplexed session subsequently
                     established on that transport connection.  This
                     value must be non-zero.

3.6     Session Startup

Process as follows:

       CurrentWindow = InitialWindowSize
       GrantedUnits  = 0

4.0    Example Receiving Implementations

The following two examples illustrate receiving implementations of varying 
degrees of complexity.  These are not meant to be complete implementation
but rather serve to illustrate the protocol.

NOTE: The examples are independent of the buffering model ( buffers may
      be deterministicly or statistically committed)
      
NOTE: The examples assume a process model where each event processes to
      completion without being preempted by another event.

4.1    Fixed Pacing Example

Consider the following variables, in addition to InitialWindowSize
and CurrentWindow and FCACKOwed:
 
   GrantDelayed     - Boolean
   GrantedUnits     - Outstanding Units
   
The following section describes how various events are processed in this 
example implementation:
   
4.1.1  Circuit Startup

       CurrentWindow    = InitialWindowSize
       FCACKOwed        = FALSE
       GrantDelayed     = FALSE
       GrantedUnits     = 0
       Repeat Window Operator
       
4.1.2  Check Buffers Available

       Can my implementation afford to grant CurrentWindow just now?
      
4.1.3  Buffers Become Available

       IF Check Buffers Available THEN
          Send FCIND( Repeat Window)
          GrantDelayed = FALSE    
       ELSE
          Wait on buffers to become available (LIFO)
       ENDIF

4.1.3  Repeat Window Operator             

       IF Check Buffers Available THEN
           Send FCIND( Repeat Window)
       ELSE           
          GrantDelayed = TRUE
          Wait on buffers to become available (FIFO)
       ENDIF
    
4.1.4  Send FCIND( operator)

       GrantedUnits += CurrentWindow
       FCACKOwed     = TRUE
       Encode and Transmit FCIND piggybacked or as IFCIND
    
4.1.5  A Frame Arrives from Sender

       GrantedUnits--;
       IF frame is FCACK THEN
          IF FCACKOwed THEN
             FCACKOwed = FALSE
          ELSE
             Protocol Violation
          ENDIF   
       ENDIF
       IF NOT GrantDelayed THEN
          IF GrantedUnits <= CurrentWindow THEN
              IF FCACKOwed THEN
                Protocol Violation
              ELSE
                Repeat Window Operator
              ENDIF
          ENDIF   
       ENDIF
       
4.2    Adaptive Pacing Example

The following example illustrates a receiving implementation that adjusts
the window size and granted units based on buffer availability and transport 
utilization.

NOTE: This example ignores other factors which might compel the receiving
      implementation to adjust the window size (i.e.  Outbound queue
      length, traffic priority, ...)      

Consider the following variables, in addition to InitialWindowSize,
CurrentWindow and FCACKOwed:
 
   GrantDelayed     - Boolean
   GrantedUnits     - Outstanding Units
   
4.2.1  Circuit Startup

       CurrentWindow    = InitialWindowSize
       FCACK            = FALSE
       GrantDelayed     = FALSE
       GrantedUnits     = 0
       Repeat Window Operator
       
4.2.2  Check Buffers Available ( X)

       Can my implementation afford to grant X units just now?
      
4.2.3  Buffers Become Available

       IF Check Buffers Available THEN
          CurrentWindow--;
          Send FCIND( Decrement Window)
          GrantDelayed = FALSE    
       ELSE
          Wait on buffers to become available (LIFO)
       ENDIF

4.2.4  Repeat Window Operator             

       IF Check Buffers Available (CurrentWindow) THEN
           Send FCIND( Repeat Window)
       ELSE           
          GrantDelayed = TRUE
          Wait on buffers to become available (FIFO)
       ENDIF
    
4.2.5  Increment Window Operator

       IF Check Buffers Available ( CurrentWindow + 1) THEN
           CurrentWindow++
           Send FCIND( Increment Window)
       ELSE
           Repeat Window Operator
       ENDIF
       
4.2.6  Send FCIND( operator)

       FCACKOwed     = TRUE
       GrantedUnits += CurrentWindow
       Encode and Transmit FCIND piggybacked or as IFCIND
    
4.2.7  An FCACK Arrives from Sender

       GrantedUnits--;
       IF NOT FCACKOwed THEN
          Protocol Violation
       ENDIF
       FCACKOwed = FALSE;
       IF NOT GrantDelayed THEN
          IF GrantedUnits < CurrentWindow THEN
              Increment Window Operator                
          ELSE IF GrantedUnits == CurrentWindow THEN
              Repeat Window Operator
          END   
       ENDIF
       
4.2.8  A Non-FCACK Frame Arrives from Sender      
       GrantedUnits--;
       IF NOT GrantDelayed THEN
          IF FCACKOwed THEN
             IF GrantedUnits < CurrentWindow THEN
                Protocol Violation
             END   
          ELSE
             IF GrantedUnits <= CurrentWindow THEN
                Repeat Window Operator
             ENDIF
          ENDIF
       ENDIF

4.2.9  Example Flows from the Above Implementation

-----SENDER-----                     ----RECEIVER----
Granted   Window                     Window   Granted  
  0         2   circuit established    2         0
  2         2   <-------- FCIND(Rpt)   2         2
  1         2   FCACK-------------->   2         1
  4         3   <-------- FCIND(Inc)   3         4
  3         3   FCACK-------------->   3         3
                       +- FCIND(Rpt)   3         6
  2         3   DATA---|----------->   3         5  
  1         3   DATA---|----------->   3         4  
  4         3   <------+
  3         3   FCACK-------------->   3         3
  6         3   <-------- FCIND(Rpt)   3         6
  5         3   FCACK-------------->   3         5
  4         3   DATA--------------->   3         4  
  3         3   DATA--------------->   3         3 
                       +- FCIND(Rpt)   3         6
  2         3   DATA---|----------->   3         5  
  1         3   DATA---|----------->   3         4  
  0         3   DATA---|----------->   3         3 
  3         3   <------+
  2         3   FCACK-------------->   3         2
  6         4   <-------- FCIND(Inc)   4         6
  5         4   FCACK-------------->   4         5
  4         4   DATA--------------->   4         4  
                                     Waiting on Buffer
                       +- FCIND(Dec)   3         7
  3         4   DATA---|----------->   3         6  
  2         4   DATA---|----------->   3         5  
  1         4   DATA---|----------->   3         4 
  0         4   DATA---|----------->   3         3 
  3         3   <------+
  2         3   FCACK-------------->   3         2
                                     Waiting on Buffer
                       +- FCIND(Dec)   2         4
  1         3   DATA---|----------->   2         3  
  0         3   DATA---|----------->   2         2  
  2         2   <------+
  1         2   FCACK-------------->   2         1
  4         3   <-------- FCIND(Inc)   3         4
  3         3   FCACK-------------->   3         3
  6         3   <-------- FCIND(Rpt)   3         6
  5         3   FCACK-------------->   3         5
  4         3   DATA--------------->   3         4  
  3         3   DATA--------------->   3         3 
  6         3   <-------- FCIND(Rpt)   3         6

5.0     Other Considerations

5.1     Backwards Compatibility

Data Link Switching nodes which do not support capabilities exchange may 
be assumed to have the following flow control support:

1.  The node can receive ENTER_BUSY and EXIT_BUSY and will stop and start
    (respectively) sending I-frame traffic to the x_BUSY originator on the
    specified circuit.  The node may also send ENTER_BUSY and EXIT_BUSY.

2.  The node supports x_BUSY messages in the circuit state
    CONNECTED, and does not run pacing on circuits using x_BUSY.

The trigger conditions for sending x_BUSY and exactly how fast a node reacts
to x_BUSY are implementation-defined.  Some nodes may buffer frames,
while others may simply use these signals to directly reflect data link
RR/RNR conditions.
 
Standard DLSw nodes which wish to interoperate with pre-standard nodes
must be able to:

1.  Discern a partner node's pre-standard status.

2.  Assume the function of a pre-standard node for circuits with that
    partner, as defined above.  Having the capability to send x_BUSY
    is not required.

When using x_BUSY on connections with pre-standard nodes, a standard
DLSw node will simultaneously use pacing on connections with other
standard nodes.

5.2     Management Considerations

Management function for flow control ( i.e. SNMP MIB objects to
control initial window sizes...) are to be defined in the overall
management specification for Data Link Switching, and, therefore, beyond
the scope of this document.

5.3     Protocol Violations

The following events shall be considered protocol violations and should 
result in sending a HALT_DL_NOACK to the offender:

1.  Sender exceeds granted units or does not acknowledge FCIND on first
    frame after its receipt (the receiver can not discern the difference
    between the two).
    
2.  Receiver does not follow a Reset Window Operator with an Increment
    Window Operator.
    
3.  Receiver has two unacknowledged FCINDs ( other than Reset Window)
    outstanding.
    
4.  Receiver sends Decrement Window Operator with a window size of one.